﻿// BT1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include"stdio.h"
#include"conio.h"
#include "math.h"
#define MAX 100

bool V[MAX];
int nV;

typedef struct
{
	int v1;
	int v2;
	float w;
}EDGE;

EDGE T[MAX];
int nT;

struct DIEM
{
	int x;
	int y;
};
DIEM * MANGDIEM;

struct Graph
{
	int n;
	double L[100][100];
};

void DocTapTin(Graph &g,char * tenfile)
{

	FILE *f=fopen(tenfile,"rt");
	if(f==NULL)
	{
		printf("khong mo duoc tap tin %s\n",tenfile);
		return;
	}

	fscanf(f,"%d",&g.n);
	MANGDIEM= new DIEM[g.n];
	for(int i=0;i<g.n;i++)
	{
		fscanf(f,"%d",&MANGDIEM[i].x);
		fscanf(f,"%d",&MANGDIEM[i].y);
	}

	fclose(f);
}

double KhoangCach(DIEM A,DIEM B)
{
	return sqrt((double)(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

void NapMaTran(Graph &g)
{
	for(int i=0;i<g.n;i++)
	{
		g.L[i][i]=0;
	}
	for(int i=0;i<g.n-1;i++)
	{
		for(int j=i+1;j<g.n;j++)
		{
			g.L[j][i] = g.L[i][j] = KhoangCach(MANGDIEM[i],MANGDIEM[j]);
		}
	}
}

void XuatMaTran(Graph &g)
{
	for(int i=0;i<g.n;i++)
	{
		for(int j=0;j<g.n;j++)
		{
			printf("%3.2lf ",g.L[i][j]);
		}
		printf("\n");
	}
}

void PrimAlg (Graph &g)
{
	nT = 0;
	for( int i = 0 ; i < g.n; i++)
	{
		V[i] = false;
	}
	V[0] = true;
	while(nT < g.n - 1)
	{
		EDGE eMin;
		int iMinWeight = -1;
		for(int i = 0 ; i < g.n; i++)
		{
			if(V[i] == false)
			{
				for(int j = 0 ; j < g.n; j++)
				{
					if(V[j] == true && g.L[i][j] != 0)
					{
						if(iMinWeight == -1 || iMinWeight >
							g.L[i][j])
						{
							eMin.v1 = i;
							eMin.v2 = j;
							eMin.w = g.L[i][j];
							iMinWeight = g.L[i][j];
						}
					}
				}
			}
		}
		if(iMinWeight == -1)
		{
			printf("Do thi khong lien thong");
		}
		else
		{
			T[nT] = eMin;
			nT++;
			V[eMin.v1] = true;
		}
	}
}

void ShowTree(EDGE E[MAX], int nE)
{
	// trong luong cay khung
	float iWeight = 0;
	for(int i = 0 ; i < nE; i++)
	{
		iWeight += E[i].w;
	}
	printf("Trong luong cay khung nho nhat: %f\n",iWeight);
	printf("Danh sach canh trong cay khung nho nhat\n"); 
	for(int i = 0 ; i < nE; i++) 
	{
		printf("(%d;%d)\n",E[i].v1+1,E[i].v2+1);
	}
}

void XuatFile(EDGE E[MAX], int nE, char * tenfile)
{
	FILE *f=fopen(tenfile,"wt");
	if(f==NULL)
	{
		printf("khong mo duoc tap tin %s\n",tenfile);
		return;
	}

	float iWeight = 0;
	for(int i = 0 ; i < nE; i++)
	{
		iWeight += E[i].w;
	}
	fprintf(f,"%d %.2f\n", nE, iWeight);

	for(int i = 0 ; i < nE; i++)
	{
		fprintf(f,"%d %d\n", MANGDIEM[E[i].v2].x, MANGDIEM[E[i].v2].y);
	}
	fprintf(f,"%d %d\n", MANGDIEM[E[nE-1].v1].x, MANGDIEM[E[nE-1].v1].y);
}

int _tmain(int argc, _TCHAR* argv[])
{
	Graph g;
	DocTapTin(g,"THANHPHO.INP");
	NapMaTran(g);
	PrimAlg(g);
	XuatFile(T,nT, "THANHPHO.OUT");
	return 0;
}